#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        vector<int> dp;
        dp.emplace_back(triangle[0][0]);
        int n = triangle.size();
        for (int i = 1; i < n; i++)
        {
            int m = triangle[i].size();
            vector<int> tmp(m);
            for (int j = 0; j < m; j++)
            {
                int down = ((j - 1) < 0) ? INT_MAX : dp[j - 1];
                int cur = (j < (m - 1)) ? dp[j] : INT_MAX;
                tmp[j] = min(down, cur) + triangle[i][j];
            }
            dp = tmp;
        }

        int res = INT_MAX;
        for (auto e : dp) res = min(res, e);
        return res;
    }
};